package problem62;

//62.不同路劲
//https://leetcode.cn/problems/unique-paths/

class Solution {
    int[][] dp;
    int m,n;
    public int uniquePaths(int _m, int _n) {
        m = _m;
        n = _n;
        dp = new int[m][n];
        return dfs(m-1, n-1);
    }
    public int dfs(int x, int y) {
        if(x == 0 || y == 0) return 1;
        if(dp[x][y] != 0) return dp[x][y];
        dp[x][y] = dfs(x-1, y) + dfs(x, y-1);
        return dp[x][y];
    }
}